ABC319 D
解説を読んだ
あるウィンドウ幅$ Wに対する行数は、$ O(N)で求まる
これがまず分かっていなかった
行いっぱいに、単語を敷き詰めていく方法を考えると、1通りである
それを貪欲に行うと、計算量は必然的に$ O(N)となる
探索すべきウィンドウ幅の範囲
分かった！
ウィンドウ幅は、「全ての単語を1行に収められる最小の幅」から「全ての単語を1行ずつ収められる最小の幅」までで考えれば良い
すべての単語を1行に収める場合、$ \max W=-1 +\sum (1 + L_i)
各単語を1行ずつに収める場合、$ \min W = \max L_i
単にウィンドウ幅を線形探索すると間に合わない
★ ウィンドウ幅を増やす場合、行数は（広義）単調減少する
★ 二分探索で間に合うようになる
行数が単調減少する性質と、行数を高速に探索したいという要請を合致させたい
ウィンドウ幅の探索範囲と、行数を求める処理を書いた
二分探索の書き方が分からない
ミスは根本的に避けたい